1. Field of the Invention
The present invention relates to a sparse variable optimization device, a sparse variable optimization method, and a sparse variable optimization program for optimizing variables of a sparse structure having a constraint that many of variables to be optimized are zero.
2. Description of the Related Art
Optimization of convex functions is a basic technique employed in various fields such as machine learning, signal processing, pattern recognition, and financial engineering. Particularly in optimization problems dealing with large-scale variables in recent years, optimization with a sparsity constraint that many variables are zero in an optimum solution is important.
As an example, when modeling health risk scores by a logistic regression model and optimizing it, the model needs to be controlled so that only risk-contributing variables are nonzero and non-risk-contributing variables are zero. In this way, for instance, which health examination items are risk-contributing can be modeled.
As another example, when analyzing correlations in network traffic, analysis of a precision matrix (the inverse of a covariance matrix) is typically carried out. Upon computing the precision matrix, the problem needs to be solved with a constraint that variables that are truly not in dependency relationships are zero. This is also a convex function optimization problem having a sparsity constraint on variables.
A convex function optimization problem having a sparsity constraint is normally a combinatorial optimization problem. In other words, this optimization problem is a problem of optimizing a combination indicating which variables are zero and which variables are nonzero. In a large-scale case, it is virtually impossible to obtain a strict solution due to computational time. Accordingly, two main types of approximate optimization methods have typically been proposed.
One method is a method of approximating the sparsity constraint by a convex function to convert the whole optimization problem to convex optimization. The most representative example is a method in which a constraint that there are many nonzero elements of variables is replaced with a constraint that an L1 norm of variables is small. The L1 norm mentioned here is a convex function.
Examples of such a method include: linear regression model optimization having a sparsity constraint (lasso, see Non Patent Literature (NPL) 1); logistic regression model optimization (L1 logistic regression, see NPL 2); and precision matrix optimization (graph lasso, see NPL 3). A fundamental idea common to these methods is to facilitate computation by approximating the original combinatorial optimization problem to another optimization problem that is easy to solve and solving the problem.
The other method is a method that improves an optimum solution search method, and is commonly referred to as “greedy search”. For instance, in a search technique called “orthogonal matching pursuit (OMP)” described in NPL 4, starting from a state where all variables are zero, variables that minimize an objective function of optimization are added forward one by one.
Forward-backward greedy search (FoBa, see NPL 5 and NPL 6) has also been proposed in recent years. This method adds a search process of deleting an added variable by some criterion between the forward processes such as OMP, and has been proved to have theoretically excellent features.